package com.github.yangyishe.p600;

import com.github.yangyishe.TreeNode;

/**
 * 543. 二叉树的直径
 * https://leetcode.cn/problems/diameter-of-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked
 * 已解决，但效率较低。推测如果改用节点存储深度可能会更快
 *
 * 给你一棵二叉树的根节点，返回该树的 直径 。
 *
 * 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
 *
 * 两节点之间路径的 长度 由它们之间边数表示。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [1,2,3,4,5]
 * 输出：3
 * 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
 * 示例 2：
 *
 * 输入：root = [1,2]
 * 输出：1
 *
 *
 * 提示：
 *
 * 树中节点数目在范围 [1, 104] 内
 * -100 <= Node.val <= 100
 *
 */
public class Problem543 {
    public static void main(String[] args) {
        TreeNode treeNode=TreeNode.getInstanceNew(new Integer[]{1,2,3,4,5});

        Problem543 problem543 = new Problem543();
        int diameterOfBinaryTree = problem543.diameterOfBinaryTree(treeNode);
        System.out.println("diameterOfBinaryTree = " + diameterOfBinaryTree);

    }

    /**
     * 思路：
     * 任意两个节点之间的路径长度，必定等于两个节点距离其最近公共父节点的长度之和
     *
     * 同时，一个父节点下的直径，等于Math.max(左子节点的直径，右子节点的直径，if(有左子节点分支，左子节点最大深度+1，0)+if(有右子节点分支，右子节点最大深度+1，0))
     *
     * @param root
     * @return
     */
    public int diameterOfBinaryTree(TreeNode root) {
        return findDia(root);
    }

    public int findDia(TreeNode treeNode){
        if(treeNode==null){
            return 0;
        }
        int leftDia=findDia(treeNode.left);
        int rightDia=findDia(treeNode.right);

        int midDia=(treeNode.left!=null?findDepth(treeNode.left)+1:0)+(treeNode.right!=null?findDepth(treeNode.right)+1:0);

        return Math.max(Math.max(leftDia,rightDia),midDia);
    }

    public int findDepth(TreeNode treeNode){
        if(treeNode==null){
            return -1;
        }
        return Math.max(findDepth(treeNode.left),findDepth(treeNode.right))+1;
    }


}
